Discussion:Théorème des quatre couleurs

Remarques diverses

c'est quoi le plus rapide algorithme pour la coloration d'une carte? --196.206.123.23 22 octobre 2006 à 18:29 (CEST)

Il me semble que la phrase suivante est vide de sens,: "En 1940, Danilo Blanuša propose un graphe dont chaque sommet est l'extrémité d'exactement trois arêtes ; ce graphe démontre l'impossibilité d'un théorème des trois couleurs." Il est évident qu'un tel graphe planaire existe déjà avec quatre sommets et il est évident qu'il n'y a pas de théorème des 3 couleurs. Je ne comprends pas ce que ce Danilo Blanuša a démontré. --130.104.1.164 26 mars 2007 à 00:52 (CEST)

En 2000, Ashay Dharwadker, un mathématicien Indien, a découvert une nouvelle preuve du théorème des quatre couleurs [1]. --122.163.103.14 11 mai 2007 à 12:10 (CEST)

---

A propos de la carte en exemple, on aurait pas 5 couleur avec l'ocean ? L'ocean compte comme une region.

Certes, mais le théorème est quand même vrai. Par exemple, tu peux remarquer qu'il est possible de choisir une couleur pour l'océan (par exemple jaune) et d'intervertir la couleur de quelques régions (par exemple 24 et 38) pour que cela marche. Valvino ^(discuter) 9 septembre 2008 à 17:48 (CEST)

---

Elle est pas terrible, l'intro, pour qui ne connait rien a ces problèmes. Ne faudrait il pas la simplifier et ajouter un paragraphe type "description" avec les pb de vocabulaire, l'explication et les considération de NP complétude ?

Y'a plein de trucs très contestables là-dedans. Déjà, cette histoire de "colorer" : en français (et en théorie des graphes), tout le monde dit "coloration", "colorable", et "coloriage". Ca, c'est indiscutable. Le TLF (par exemple), donne les deux verbes, mais la fréquence de colorer est bien plus élevée. Donc, le plus simple est de dire que dans le contexte de la théorie des graphes, on emploie "colorer" sans se lancer dans des justifications qui, de toute façon, ne sont qu'un POV... et de demander une référence...

Ensuite, la référence à la preuve "ni acceptée ni invalidée" de Spencer-Brown est un scandale : vieille de quarante ans, cette histoire n'a jamais convaincu ... que Spencer-Brown. Au mieux, je veux bien le donner comme exemple des nombreuses (moins que pour Fermat ou la quadrature du cercle, tout de même) tentatives d'amateurs plus ou moins farfelus d'attaquer ce difficile problème (et si Erdös le pensait, ça devrait convaincre la plupart des gens de bonne foi)

Par contre, ça manque sérieusement de référence au traval d'Heawood. Je vais voir si j'ai le temps Dfeldmann (d) 19 juillet 2009 à 07:56 (CEST)

Camembert

En dimension 2, un camenbert est-il un connexe? Si je regarde la définition de connexe, je pense que oui (mais je dois me tromper sinon cet article est faux). Donc si la réponse est oui, un camenbert avec disons 5 secteurs ne peut être colorié avec 4 couleurs. Où est la faille? Skiff (d) 19 juillet 2009 à 10:34 (CEST)

Bien sûr, deux régions n'ayant qu'un point en commun peuvent être coloriés de la même façon. Mais tu as parfaitemeñt raison, ce point doit clairement être précisé, sans doute dans l'intro. Je m'y mets tout de suite Dfeldmann (d) 19 juillet 2009 à 17:20 (CEST)

Le théorème est faux

Je viens de trouver un contre exemple dans lequel 5 couleurs sont nécessaires Voici le lien de l'image : http://www.imagup.com/pics/1267006423.html Le pays entouré de lignes noires a besoin d'une cinquième couleur : il ne peut être ni jaune, ni vert, ni bleu, ni rouge. .Pourquoipasgne

Pas la peine de revoir l'article à partir de zéro pour autant : versez un pot de peinture jaune sur votre pays bleu, et la situation devrait se débloquer :-). Bon, je vous réponds avec plaisir, mais n'oublions pas que ces pages sont conçues pour faire avancer les articles, je vous propose donc de ne pas partir dans un dialogue, de s'arrêter là. Touriste (d) 23 février 2010 à 21:47 (CET)

Carte corrigée. Le pays rouge est semblable à la partie de la Russie située en Europe, indissociable de sa couleur rouge. Effectivement, 5 c'est le maximum que j'ai trouvé pour l'instant par contre.

Pas la peine de chercher aussi loin, la carte de la Russie proposée comme illustration du théorème est elle-même un contre-exemple, en témoigne les régions 48,62 et 52 qui sont 3 régions distinctes mais qui sont toutes colorées en bleu alors qu'elles sont adjacentes.

Tout ce que ça prouve, c'est que le programme de coloration de cette carte de Russie s'est planté...

Solution : intervertir les couleurs de 13 et 21, puis colorier 62 en jaune.

Bdc43 (d) 27 octobre 2010 à 14:45 (CEST)

Le contre exemple ne fonctionne pas : il suffit de colorer le petit pays en bleu (a la place du rouge) pour debloquer la situation (et donc le rouge va a la place du blanc). 163.5.72.241 (d) 1 mai 2011 à 23:40 (CEST)

Exemple de la carte du monde

La carte du monde proposée dans l'article ne respecte pas le théorème: deux pays adjacents d'Afrique sont jaunes. Quelqu'un aurait-il une version corrigée?

« Colorer » ou « colorier »

Il me semble que le verbe adéquat quand il s'agit d'appliquer des couleurs à un graphe est colorier et non pas colorer. --Pierre de Lyon (discuter) 17 mars 2016 à 11:16 (CET)

C'est sans doute une instance de franglais.

Contre ce même défaut, en français, le sucre est soluble dans l'eau et un problème est résoluble quand on peut le résoudre (et non le"solutionner"). JC.Raoult (discuter) 5 octobre 2022 à 12:45 (CEST)

Et un programme qui sert à « interpréter » un programme s'appelle un interprète et non pas un interpréteur. --Pierre Lescanne (discuter) 5 octobre 2022 à 17:40 (CEST)

Proposition d'anecdote pour la page d'accueil

Une proposition d'anecdote pour la section « Le Saviez-vous ? » de la page d'accueil, et basée sur cet article, a été proposée sur la page dédiée.
N'hésitez pas à apporter votre contribution sur la rédaction de l'anecote, l'ajout de source dans l'article ou votre avis sur la proposition. La discussion est accessible ici.
Une fois l'anecdote acceptée ou refusée pour publication, la discussion est ensuite archivée là.
(ceci est un message automatique du bot GhosterBot le 05 juin 2017 à 08:16)

Coloriage de graphes vs coloriage de cartes

Le problème des quatre couleurs traite de coloriage de cartes (ou de graphes planaires). Le paragraphe Pratique cite des applications du coloriage de graphe, ce qui n'est pas le même problème. J'aurais envie d'enlever ce paragraphe qui en l'état actuel ne peut que perturber le lecteur. Qu'en pensez-vous? --Pierre de Lyon (discuter) 28 novembre 2017 à 17:58 (CET)

Je suis d'accord. Il faudrait voir si l'article sur la coloration de graphe peut profiter des exemples de cette sections... --Roll-Morton (discuter) 29 novembre 2017 à 18:51 (CET)

Je te laisse le faire, c'est plus ton domaine. --Pierre de Lyon (discuter) 30 novembre 2017 à 09:27 (CET)

--Roll-Morton (discuter) 30 novembre 2017 à 11:06 (CET)

lien avec les graphes bipartis planaires

Bonjour

Ce théorème me rappelle instinctivement une énigme géométrique. Il faut relier 3 points A B et C avec 3 points X Y et Z dans un plan. On obtient donc 9 courbes (AX AY AZ BX BY BZ CX CY CZ). La contrainte est qu'aucune courbe ne doit se couper. Si j'ai bien compris il s'agit de construire un graphe "biparti complet et planaire" ce qui serait impossible. Dans l'introduction il est question de "la coloration [...] des sommets d'un graphe planaire". Est ce qu'il s'agissait en fait de ce problème?

--Bcornet03 (discuter) 13 août 2020 à 07:43 (CEST)

Bonjour Bcornet03  ; ce problème, c'est l'énigme des trois maisons, et son impossibilité provient du fait que le graphe biparti complet nommé traditionnellement $K_{3,3}$ n'est pas planaire (ça, c'est un bout du théorème de Kuratowski, lui-même point de départ du puissant théorème de Robertson-Seymour). Mais cela dit, tout cela n'a hélas qu'assez peu de rapport avec les questions de coloration de graphe...--Dfeldmann (discuter) 13 août 2020 à 08:51 (CEST)

merci de ta réponse. Bon alors dans ce cas je ne comprends pas la phrase d'introduction "la coloration [...] des sommets d'un graphe planaire", que signifie colorer un sommet? Je ne sais pas si je manque d'infos ou si c'est juste la phrase qui est mal écrite. D'autre part il me semble percevoir comme lien entre les deux problèmes que pour un continent avec seulement 5 pays, on peut prouver par le théorème de Kuratowski que 4 couleurs seulement seront nécessaires. Mais si je comprends bien c'est la généralisation à N pays qui pose problème? En fait j'avoue que dans l'introduction la phrase " il ne peut exister cinq régions connexes deux à deux adjacentes" m'a parue dans un premier temps une preuve suffisante au théorème des 4 couleurs. Donc peut être qu'il faudrait présenter le théorème de Kuratowski un peu différemment pour qu'on se rende compte qu'il ne suffit pas à justifier le théorème? D'une manière plus générale, je pense que ce théorème est assez rigolo et qu'il peut intéresser des novices en maths (comme moi) mais en même temps il invoque des connaissances assez complexes donc c'est peut être juste pour ça que je ne saisi pas tout.

--Bcornet03 (discuter) 13 août 2020 à 14:48 (CEST)

Rebonjour, Bcornet03. Bon, comme très souvent en mathématiques, il faut revenir aux définitions pour être sûr de ne pas être victime de malentendus, d'intuitions valables seulement pour des objets familiers, ou d'images simplificatrices, mais erronées. Ici, la clé, c'est notre bel article Coloration de graphe, donnant des définitions rigoureuses (je vais d'ailleurs rajouter ce lien ici). Ensuite, l'impossibilité de 5 régions, chacune touchant les quatre autres, c'est effectivement Kuratowski (plus précisément, le fait que le graphe $K_{5}$ n'est pas planaire), mais bien sûr c'est très loin de montrer le théorème, ni même la version (corrigée) de Kempe. On peut effectivement détailler plus, en donnant par exemple une carte difficilement coloriable en quatre couleurs, mais par définition, un contre-exemple n'existant pas, il est difficile de montrer une carte prouvant l'erreur de Kempe... Non, à part la terminologie, il n'y a rien de compliqué dans l'énoncé du théorème ; ce qui est dur (pour ne pas dire plus) , c'est sa démonstration, ou encore les généralisations (sur le tore à n trous, par exemple) qu'on peut en faire. Cordialement,--Dfeldmann (discuter) 13 août 2020 à 15:56 (CEST)

Bonjour Dfeldmann, effectivement l'article sur la coloration des sommets éclaircie parfaitement ma pensée! Merci de ton aide et belle journée. --Bcornet03 (discuter) 14 août 2020 à 07:01 (CEST)

Proposition d'anecdote pour la page d'accueil

Une anecdote basée sur cet article a été proposée ici (une fois acceptée ou refusée elle est archivée là). N'hésitez pas à apporter votre avis sur sa pertinence, sa formulation ou l'ajout de sources dans l'article.
Les anecdotes sont destinées à la section « Le Saviez-vous ? » de la page d'accueil de Wikipédia. Elles doivent d'abord être proposées sur la page dédiée.
(ceci est un message automatique du bot GhosterBot le 05 mai 2021 à 21:46, sans bot flag)

Kuratovski

Je ne comprends pas la remarque entre parenthèses à la fin du deuxième paragraphe : "Par ailleurs, il ne peut exister 5 régions deux à deux adjacentes (c'est la partie simple du théorème de Kuratovski)". Elle donne l'impression que le théorème des quatre couleurs est plus large, alors que pour le démontrer, il faut et il suffit de démontrer (me semble-t-il) qu'on ne peut pas avoir plus de 4 régions adjacentes 2 à 2 justement, donc les 2 propositions sont équivalentes. Ou est-ce que j'ai loupé quelque chose ? ISIDORODOR (discuter) 24 avril 2023 à 22:45 (CEST)